package basic.study.wantOffer.chapter5;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @ClassName Problem41
 * @Description 如何得到一个数据流中的中位数？
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/25 9:52
 * @Version 1.0
 */
public class Problem41 {
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();//小顶堆，默认容量为11
    PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>() {//大顶堆，容量11
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void Insert(Integer num) {
        if (((minHeap.size() + maxHeap.size()) & 1) == 0) {//偶数时,下个数字加入小顶堆
            if (!maxHeap.isEmpty() && maxHeap.peek()>num) {
                maxHeap.offer(num);
                num = maxHeap.poll();
            }
            minHeap.offer(num);
        } else {//奇数时，下一个数字放入大顶堆
            if (!minHeap.isEmpty() && minHeap.peek() < num) {
                minHeap.offer(num);
                num = minHeap.poll();
            }
            maxHeap.offer(num);
        }
    }

    public Double GetMedian() {
        if ((minHeap.size() + maxHeap.size()) == 0) {
            throw new RuntimeException();
        }
        double median;
        if (((minHeap.size() + maxHeap.size())&1)==0) {
            median = (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            median = minHeap.peek();
        }
        return median;
    }
}
